package com.zhongge.customheap;

import java.util.Arrays;

/**
 * @ClassName MyHeap
 * @Description TODO 自定义堆
 * @Author 笨忠
 * @Date 2025/9/6 10:10
 * @Version 1.0
 */
public class MyHeap {
    //使用数组存储堆
    private int[] elem;
    //但凡有数组必定有usedSize
    private int usedSize;

    public MyHeap() {
        this.elem = new int[10];
    }

    //各种方法

    /**
     * 将数据构建为完全二叉树
     * @param array 数据的存放
     */
    public void initHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     * 创建大根堆
     */
    public void createMaxHeap() {
        //从最后一个非叶子节点开始 到 根节点结束
        for (int parent = (usedSize-1 - 1) / 2; parent >= 0; parent--) {
            //调整为大根堆：向下调整
            /**
             * parent：开始的位置
             * usedSize：后面会用做为调整的结束条件
             */
            shiftDown(parent, usedSize);
        }
    }
    /**
     * 向下调整 一次路径
     * @param parent 这次路径调整的开始位置
     * @param usedSize 这次路径调整的结束位置
     */
    private void shiftDown(int parent, int usedSize) {
        //首先知道父节点 求 孩子节点
        int child = 2*parent + 1;
        //那么一次调整的过程到什么时候结束呢？？
        while (child < usedSize) {
            //接下来就是 找出最大的孩子与父节点比
            //看一下：最大的孩子是谁？
            //然child始终指向最大的孩子
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child++;//确保child始终指向的是最大的孩子
            }
            //程序走到这里，那么说明child所指的元素就是最大的孩子节点
            //此时我们只需要和父节点比较
            if(elem[child] > elem[parent]) {
                //如果孩子节点大于父节点 那么就交换
                //交换我们将他单独将他作为一个函数
                swap(child,parent);
                //注意：交换完后==》不确定给路径往下是否达到大根堆
                //所以父和子得继续往下移动
                parent = child;//父亲来到孩子的位置
                child = 2*parent + 1;//由父亲求出新的孩子
            } else {//如果满足大根堆，那么结束本次路径的调整
                break;
            }
        }

    }
    /**
     * 交换两个数
     * @param i  第一个值的下标i
     * @param j  第二个值的下标j
     * 注意：交换我们只有将下标传进去才可以交换
     */
    private void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    /**
     * 插入元素到大根堆
     * @param val 插入值
     */
    public void offer(int val) {
        //1.判满扩容
        if (isFull()) {
            //扩容
            this.elem = Arrays.copyOf(elem, 2*elem.length);
        }
        //将数值插入
        elem[usedSize] = val;
        //调整为大根堆 和 usedSize++
        /**
         * 起点：usedSize
         * 终点：0
         */
        shiftUp(usedSize, 0);
        usedSize++;//插入一个就usedSize++
    }

    /**
     * 先上调整
     * @param child 起点
     * @param i 终点
     */
    private void shiftUp(int child, int i) {
        //根据孩子(起点) 求 父节点
        int parent = (child - 1) / 2;
        //什么时候调整结束？
        while (parent >= i) {//只有parent>=0的时候才调整，当parent<0的时候就结束了
            //此时只需要待插入节点和父节点直接比较即可，而无需与孩子节点比较
            if (elem[child] > elem[parent]) {
                swap(child, parent);//交换

                //此时不知道 该向上的路径是否已经符合大根堆了，所以我们继续调整
                //父和子同时向上：向上先动子（防止子找不到父）
                child = parent;
                parent = (child - 1)/2;
            } else {//如果不大于 那么就直接结束路径调整
                break;
            }
        }
    }

    /**
     * 判满
     * @return true-满 false-不满
     */
    private boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 优先级队列的出队：大根堆的删除堆顶元素
     * @return 删除的值
     */
    public int poll() {
        //第一步 判空：如果空就没必要删除了
        if (isEmpty()) {
            throw new RuntimeException("堆为空");
        }
        //将堆顶元素先存起来 待会返回
        int del = elem[0];
        //将堆顶元素和最后一个元素交换
        swap(0, usedSize - 1);
        //然后usedSize--
        usedSize--;
        //向下调整大根堆
        /**
         * 起点 ：0
         * 终点：usedSize
         */
        shiftDown(0, usedSize);
        //最后将值返回
        return del;
    }

    /**
     * 判空
     * @return true-空 false-不空
     */
    private boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取队头元素(对顶元素)
     * @return 0号元素
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("堆元素为空");
        }
        return elem[0];
    }


    //////////////////////////////////////

    /**
     * 堆的应用：堆排序
     */
    public void heapSort() {
        //第一步：使用辅助下标
        int end = usedSize - 1;
        //第二步：进行调整大根堆和交换首尾元素的循环
        while (end > 0) {
            //调整大根堆
            shiftDown(0, end);
            //交换首尾元素
            swap(0, end);
            //交换完之后 end--
            end--;
        }
    }

    public int[] getElem() {
        return elem;
    }

    public void setElem(int[] elem) {
        this.elem = elem;
    }
}
